Rosenbrock function

In mathematical optimization, the Rosenbrock function is a non-convex function used as a performance test problem for optimization algorithms introduced by Howard H. Rosenbrock in 1960[1]. It is also known as Rosenbrock's valley or Rosenbrock's banana function.

The global minimum is inside a long, narrow, parabolic shaped flat valley. To find the valley is trivial. To converge to the global minimum, however, is difficult.

It is defined by

f(x, y) = (1-x)^2 %2B 100(y-x^2)^2 .\quad

It has a global minimum at (x, y)=(1, 1) where f(x, y)=0. A different coefficient of the second term is sometimes given, but this does not affect the position of the global minimum.

Contents

Multidimensional generalisations

Two variants are commonly encountered. One is the sum of N/2 uncoupled 2D Rosenbrock problems,

f(\mathbf{x}) = f(x_1, x_2, \dots, x_N) = \sum_{i=1}^{N/2} \left[100(x_{2i-1}^2 - x_{2i})^2 %2B (x_{2i-1} - 1)^2 \right].[2]

This variant is only defined for even N and has predictably simple solutions.

A more involved variant is

f(\mathbf{x}) = \sum_{i=1}^{N-1} \left[ (1-x_i)^2%2B 100 (x_{i%2B1} - x_i^2 )^2 \right] \quad \forall x\in\mathbb{R}^N.[3]

This variant has been shown to have exactly one minimum for N=3 (at (1, 1, 1)) and exactly two minima for 4 \le N \le 7 -- the global minimum of all ones and a local minimum near (x_1, x_2, \dots, x_N) = (-1, 1, \dots, 1). This result is obtained by setting the gradient of the function equal to zero, noticing that the resulting equation is a rational function of x. For small N the polynomials can be determined exactly and Sturm's theorem can be used to determine the number of real roots, while the roots can be bounded in the region of |x_i| < 2.4 [4]. For larger N this method breaks down due to the size of the coefficients involved.

Stationary points

Many of the stationary points of the function exhibit a regular pattern when plotted[4]. This structure can be exploited to locate them.

Stochastic version

There are many ways to extend this function stochastically. In Xin-She Yang's functions, a generic or heuristic extension of Rosenbrock's function is given to extend this function into a stochastic function[5]

f(\mathbf{x}) =\sum_{i=1}^{n-1} \Big[(1-x_i)^2%2B100 \epsilon_i (x_{i%2B1}-x_i^2)^2 \Big],

where the random variables \epsilon_i (i=1,2,...,n-1) obey a uniform distribution Unif(0,1). In principle, this stochastic function has the same global optimimum at (1,1,...,1), however, the stochastic nature of this function makes it impossible to use any gradient-based optimization algorithms.

See also

Notes

  1. ^ Rosenbrock, H.H. (1960). "An automatic method for finding the greatest or least value of a function". The Computer Journal 3: 175–184. doi:10.1093/comjnl/3.3.175. ISSN 0010-4620. 
  2. ^ L C W Dixon, D J Mills. Effect of Rounding errors on the Variable Metric Method. Journal of Optimization Theory and Applications 80, 1994. [1]
  3. ^ "Generalized Rosenbrock's function". http://www.it.lut.fi/ip/evo/functions/node5.html. Retrieved 2008-09-16. 
  4. ^ a b Schalk Kok, Carl Sandrock. Locating and Characterizing the Stationary Points of the Extended Rosenbrock Function. Evolutionary Computation 17, 2009. [2]
  5. ^ Yang X.-S. and Deb S., Engineering optimization by cuckoo search, Int. J. Math. Modelling Num. Optimisation, Vol. 1, No. 4, 330-343 (2010)

References

External links